/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2023-12-13
 * Time:22:17
 */

/**
 * 动态规划:面试题 08.01. 三步问题
 * 三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
 * 示例1:
 *  输入：n = 3
 *  输出：4
 *  说明: 有四种走法
 */
public class waysToStep {
    public int waysToStep(int n) {
        int mod = (int)1e9 + 7;
        if(n <= 2){
            return n;
        }
        if(n == 3){
            return 4;
        }
        int a = 1,b = 2,c = 4,d = 0;
        for(int i = 3;i < n;i++){
            d = ((a + b) % mod + c) % mod;
            a = b;
            b = c;
            c = d;
        }
        return d % 1000000007;
    }
}
